链表——删除链表中间结点和a/b处的结点

Posted on | In ,

题目1：给定链表头节点，实现删除链表中间节点的函数。
1->2：删1
1->2->3：删2
…
若链表长度为N，则删除的节点为(N+1)/2。

实现：定位到要删除节点的前一个节点。
方法一：只需要遍历一半。找规律：链表每增加2，要删除的节点就往后移一位

  1. 对于长度小于等于2的链表，单独考虑。
  2. 对于长度大于3的链表：
    1）初始状态pre=head; cur = head.next.next;
    2）以后cur每移动两位，则pre移动一位。

方法二：需要遍历整个链表

  1. 考虑链表为空或长度为1，则返回头节点。
  2. 考虑特殊长度为2时，头节点会移动到下一个节点。
  3. 计算节点个数k，定位要删除的结点的前一个节点，j=k/2
    然后执行指针指向操作（即删除节点）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class RemoveMidNode {
	//方法一：遍历到要删除节点的前一个节点
	public static Node removeMidNode1(Node head) {
		if (head == null || head.next == null) {//如果链表尾空或只有一个节点
			return null;
		}
		if (head.next.next == null) {
			return head.next; //本来的是返回头节点，但由于头节点被删了，所以返回它的下一个节点
		}
		Node current = head;
		int k = 1; //定义k，计算当前链表的节点个数
		while(current.next != null) {
			current = current.next;
			k++;
		}
		current = head;
		int j = 0;
		while(++j != k/2) { //定位到要删除的元素的前一个元素
			current = current.next;
		}
		current.next = current.next.next;
		return head;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//方法二：遍历整个链表，找总的节点个数
public static Node removeMidNode2(Node head) {
	if (head == null || head.next == null) { //考虑链表尾空或只有一个节点
		return head;
	}
	if(head.next.next == null) { //考虑只有两个节点
		return head.next;
	}
	//查找中间节点的前一个节点
	Node previous = head;
	Node current = head.next.next;
	while(current.next != null && current.next.next != null) {
		previous = previous.next; //pre移一位
		current = current.next.next; //cur移两位
	}
	previous.next = previous.next.next; //pre后面的数正是中间数
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
	//Test
	public static void main(String[] args) {
		Node head = new Node(1); 
		Node node1 = new Node(2);
		//Node node2 = new Node(3);
		//Node node3 = new Node(4);
		head.next = node1;
		//node1.next = node2;
		//node2.next = node3;
		System.out.println(removeMidNode1(head).data); //返回头节点
		System.out.println(removeMidNode2(head).data); //返回头节点
	}
}

注意：查找前一个节点与查找中间节点的不同

1
2
3
4
5
6
7
8
//查找中间节点
Node node1 = head;
Node node2 = head;
while(node2.next != null && node2.next.next != null) {
	node1 = node1.next;
	node2 = node2.next.next;
}
//node2所指就是中间数

题目2：给定链表头节点，整数a和b，删除位于r=a/b处的节点。
若r=0或r>1不删除任何节点，
若r在区间(0,1/5]上，删除节点1；
若r在区间(1/5,2/5]上，删除节点2；
…

实现：
先计算(double)r = (double(a*n))/ (double)b
r向上取整的整数值代表需要删除的节点是第几个节点。
找到该节点的前一个节点执行删除操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static Node removeByRatio(Node head, int a, int b) {
	if (a < 0 || a > b) {
		return head;
	}
	int n = 1; //head为第一个节点
	Node current = head;
	while (current.next != null) {
		n++;
		current = current.next;
	}
	n = (int)Math.ceil(a*n / b); //n为需要删除的第n个节点
	if (n > 1) { //a和b的大小是不确定的
		current = head;
		while(--n != 1) { //找到第n个节点的前一个节点
			current = current.next;
		}
		current.next = current.next.next;
	}
	return head;
}